/** 思路：
 * 遍历树节点（广度优先）
 * 将树节点转为Array Item，push到数组
 * 根据父子关系，找到Array Item的parentId
 **/ 
interface IArrayItem {
  id: number
  name: string
  parentId: number
}
interface ITreeNode {
  id: number
  name: string
  children?: ITreeNode
}
function convert(root: ITreeNode): IArrayItem[] {
  // Map
  const nodeToParent: Map<ITreeNode, ITreeNode> = new Map()
  const arr: IArrayItem[] = []
  // 广度优先遍历，queue
  const queue: ITreeNode[] = []
  queue.unshift(root) // 根节点 入队
  while(queue.length > 0) {
    const curNode = queue.pop() // 出队
    if(curNode == null) break
    const {id, name, children} = curNode
    // 创建数组 item 并 push
    const parentNode = nodeToParent.get(curNode)
    const parentId = parentNode?.id || 0
    const item = {id, name, parentId}
    arr.push(item)

    // 子节点入队
    children.forEach(child => {
      // 映射 parent
      nodeToParent.set(child, curNode)
      // 入队
      queue.unshift(child)
    })
  }
  return arr
}